package com.str.PQ;
public class Huffman {
// Build a Huffman tree from list hufflist
  
  private static class HuffNode implements Comparable {
    char lett;  // The letter
    int freq;   // Frequency for the letter
    HuffNode left;
    HuffNode right;
	
    HuffNode() {
      lett = '\0'; 
      freq = 0;
      left = right = null;
    }
    
    public int compareTo(Object that) {
      HuffNode other = (HuffNode) that;
      return freq - other.freq;	
    }
    
    public String toString()
    { return lett + "/" + freq; }
  }
  
  private static class CodeMember {
    int freq;
    String code;

    CodeMember() {
      freq = 0;
      code = "";
    }
    
    public String toString()
    { return freq + "\t" + code; }
  }

  private static final int SYMBOLS = 256;  
  private static CodeMember[] codeTable;
  private static HuffNode root;
  
  public static void buildTree(String text) {
  	
  	codeTable = new CodeMember[SYMBOLS];    
    for (int i = 0; i < text.length(); i++) {
  	  int j = text.charAt(i);
  	  if (codeTable[j] == null)
  	    codeTable[j] = new CodeMember();
  	  codeTable[j].freq++;
	}
	PriorityQueue codePQ = new HeapPriorityQueue();  
	root = buildTree(codePQ);
  } 
	  
  private static HuffNode buildTree(PriorityQueue codePQ) {
	
    for (int i = 0; i < codeTable.length; i++)
      if (codeTable[i] != null) {
      	HuffNode temp = new HuffNode();
        temp.lett = (char) i;
        temp.freq = codeTable[i].freq;
        codePQ.add(temp);
      }
	
    while (codePQ.size() > 1) {
      HuffNode temp1 = (HuffNode) codePQ.removeMin();
      HuffNode temp2 = (HuffNode) codePQ.removeMin();
      HuffNode temp3 = new HuffNode();
      temp3.freq = temp1.freq + temp2.freq;
      temp3.left = temp1;
      temp3.right = temp2;
      codePQ.add(temp3);
    }
    return (HuffNode) codePQ.removeMin(); // Return the tree
  }
    
  public static void printCodeTable() {
    for (int i = 0; i < codeTable.length; i++)
      if (codeTable[i] != null)
        System.out.println((char) i + "\t" + codeTable[i]);
  }  
  
  public static void outputTree() {
  	String prefix = "";
    outputTree(root, prefix); 
  }

  private static void outputTree(HuffNode ref, String prefix) {
  	if (ref == null) return;
    else if (ref.left == null && ref.right == null) {	
  	  int i = ref.lett;
      codeTable[i].code = prefix;
    }
    else {
      outputTree(ref.left, prefix + "0");
      outputTree(ref.right, prefix + "1");
    }	
  } 
  
  public static String encode(String text) {
  	String code = "";
    for (int i = 0; i < text.length(); i++) {
      int j = text.charAt(i);
      if (codeTable[j] == null) {
        System.out.println("Bad input");
        return null;
      }      	
      code += codeTable[j].code;
    }
    return code;
  }
  
  public static String decode(String code) {
  	String text = "";
  	int i = 0;
  	while (i < code.length()) {
      HuffNode ref = root;
      while (ref.left != null && ref.right != null)	{ 	    
        if (code.charAt(i) == '0')
         ref = ref.left;
        else if (code.charAt(i) == '1')
          ref = ref.right;
        else {
          System.out.println("Bad input");
          return null;
        }
        i++;
      }
      text += ref.lett;
    }
    return text;	
  }
}